# -*-coding = utf-8 -*-

# @Time: 2021/4/24 18:46
# @Author: bistro
# @File: p377.py
# @Software: PyCharm
# 377.组合总和 Ⅳ
from typing import List


class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [0] * (target + 1)
        dp[0] = 1
        for j in range(1, target + 1):
            for k in range(n):
                if nums[k] <= j:
                    dp[j] += dp[j - nums[k]]
        print(dp)
        return dp[-1]


s = Solution()
s.combinationSum4([1, 2, 9], 5)
